package acwing._1_1AlgorithmBasic._5DynamicProgramming;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic._5DynamicProgramming
 * @File : Q0282.java
 * @Author : WangRuoyu
 * @Date : 2023/4/6 15:24
 */

import java.io.*;

public class Q0282 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] words = br.readLine().split(" ");
        int n = Integer.parseInt(words[0]);
        int[] s = new int[n + 1];
        int[][] f = new int[n + 1][n + 1];
        words = br.readLine().split(" ");
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + Integer.parseInt(words[i - 1]);
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i <= n - len + 1; ++i) {
                int l = i;
                int r = i + len - 1;
                f[l][r] = 0x3f3f3f3f;
                for (int k = l; k <= r - 1; ++k) {
                    f[l][r] = Math.min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }
        System.out.println(f[1][n]);
    }
}

